class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int gao = matrix.length;
        int kuan = matrix[0].length;
        int hang = 0;
        if(target > matrix[gao-1][kuan-1]) return false;
        if(target < matrix[0][0]) return false;
        for(int i = 0;i < gao;i++) {
            if(target == matrix[i][kuan-1]) return true;
            if(target < matrix[i][kuan-1]) {
                hang = i;
                break;
            }
        }
        int left = 0;
        int rigth = kuan-1;
        while(left <= rigth) {
            if(matrix[hang][left] == target) return true;
            if(matrix[hang][rigth] == target) return true;
            left++;
            rigth--;
        }
        return false;
    }
}